package dfs;

import java.util.LinkedList;

public class 连续差相同的数字 {

    //没错 但超时
//    public int[] numsSameConsecDiff(int n, int k) {
//        LinkedList<Integer> list = new LinkedList<>();
//        int start=(int)Math.pow(10,n-1);
//        int end=(int)Math.pow(10,n);
//        for (int i = start; i < end; i++) {
//            int num=0;
//            String s = String.valueOf(i);
//            for (int j = 0; j < n - 1; j++) {
//                if (Math.abs(s.charAt(j)-s.charAt(j+1))==k)
//                    num++;
//            }
//            if (num==n-1)
//                list.add(i);
//        }
//        int[] res = new int[list.size()];
//        for (int i = 0; i < list.size(); i++) {
//            res[i]=list.get(i);
//        }
//        return res;
//    }
    //成功
    LinkedList<Integer> list = new LinkedList<>();
    public int[] numsSameConsecDiff(int n, int k) {
        //初始化builder
        for (int i = 1; i < 10; i++) {
            StringBuilder builder = new StringBuilder();
            builder.append(i);
            dfs(n,k,builder);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i]=list.get(i);
        }
        return res;
    }
    private void dfs(int n, int k, StringBuilder builder) {
        if (builder.length()==n){
            list.add(Integer.parseInt(builder.toString()));
            return;
        }
        int m = builder.charAt(builder.length() - 1) - '0';
        for (int i = 0; i < 10; i++) {
            if (builder.length()==0 || i==0)
                continue;    //首位不能为0
            if (Math.abs(i-m)==k) {
                builder.append(i);
                dfs(n,k,builder);
                builder.deleteCharAt(builder.length()-1);
            }
        }
    }
}
